package chapter04_RecursionAndDynamic;

/**
 * 描述：回文最少分割数
 *      给定一个字符串str，返回将str全部切为回文子串的最小分割数
 * @author hl
 * @date 2021/9/27 20:28
 */
public class MinCut {
    public static void main(String[] args) {
        MinCut main = new MinCut();
        String str = "ACDCDCDAD";
        int res = main.minCut(str);
        System.out.println(res);
    }

    /**
     * 动态规划
     * dp[i]表示从str[i...len-1]全部且为回文子串的最小分割数，dp[0]即时答案
     * 对于dp[i]的求解，有j，i<=j<len，如果str[i...j]为回文字符串，那么str[i...j]本身就可以作为一个被切割的部分，
     * 剩下的部分str[j + 1, len - 1]寻求最优的切割方式即dp[j + 1]，
     *      因此如果str[i...j]是回文字符串，那么dp[i] = dp[j + 1] + 1，
     *      否则没有必要进行处理，因为只有str[i...j]为回文串的时候才有可能产生更小值
     *
     *      需要枚举所有以i开头的回文子串的可能性，选出最小值，因此dp[i] = min{dp[j + 1] + 1(i<=j<len ，并且str[i...j]必须为回文串)}
     *
     *      还有一个问题是如何快速判断str[i...j]是否为回文串?
     *      创建一个二维数组p[][]，如果p[i][j]为true表示为回文串，有以下几种情况：
     *      1）str[i...j]由一个字符组成
     *      2）str[i...j]由两个字符组成
     *      3）str[i...j]由两个以上字符组成，此时p[i+1][j-1]=true，并且str[i]==str[j]
     *      根据p[i][j]的判断规则，如果i是从右到左求解，而j从i开始往右求解，那么满足快速判断str[i...j]是否为回文的条件，因此这也是动态规划的顺序
     *
     * @param str
     * @return
     */
    public int minCut(String str){
        if(str == null || str.length() == 0){
            return 0;
        }
        int len = str.length();
        int[] dp = new int[len + 1];
        dp[len] = -1;
        boolean[][] p = new boolean[len][len];
        for (int i = len - 1; i >= 0; i--) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = i; j < len; j++) {
                //先判断str[i...j]是否为回文串
                if ((j - i < 2 || p[i + 1][j - 1]) && str.charAt(i) == str.charAt(j)) {
                    //每趟内层循环至少进一次
                    p[i][j] = true;
                    dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0];
    }
}
